#include <stdio.h>
#include <stdbool.h>

#define max(num1, num2) ((num1)>(num2)?(num1):(num2))

void array() {
    /**
    * 一维数组的声明
    */
    //直接声明int类型数组，容量为10
    int a[10];

    //声明后，可以赋值初始值，使用{}囊括，不一定需要让10个位置都有初始值，比如这里仅仅是为前三个设定了初始值，
    //注意，和变量一样，如果只是创建数组但是不赋初始值的话，因为是在内存中随机申请的一块空间，有可能之前其他地方使用过，保存了一些数据，所以数组内部的元素值并不一定都是0
    int b[10] = {1, 2, 4};

    //我们也可以通过 [下标] = 的形式来指定某一位的初始值，注意下标是从0开始的，第一个元素就是第0个下标位置，比如这里数组容量为10，那么最多到9
    int c[10] = {1, 2, [4] = 777, [9] = 666};

    //也可以根据后面的赋值来决定数组长度
    int d[] = {1, 2, 3};

    //多个字符
    char str[] = {'A', 'B', 'C'};

    //实际上字符串就是多个字符的数组形式
    char str2[] = "ABC";

    /**
    * 多维数组的声明
    */
    //可以看到，数组里面存放的居然是数组
    //存放的内层数组的长度是需要确定的，存放数组的数组和之前一样，可以根据后面的值决定
    int arr[2][2] = {{20, 10},
                     {18, 9}};
    //二维数组的声明可以不声明有几行但必须声明每一行有几列，就像下方这样声明。如果像 int arr3[2][]; 和 int arr4[][]; 声明都是错误的
    int arr2[][2] = {{20, 10},
                     {18, 9}};
}

//冒泡排序
void bubblingSort() {
    int arr[12] = {1, 4, 23, 52, 25, 33, 64, 43, 17, 65, 86, 13};
    //从小到大排序，下沉的顺序
    for (int i = 0; i < 11; ++i) {
        for (int j = i + 1; j < 12; ++j) {
            if (arr[i] > arr[j]) {
                int num = arr[j];
                arr[j] = arr[i];
                arr[i] = num;
            }
        }
    }

    //从小到大排序，上浮的顺序
    for (int i = 0; i < 12; ++i) {
        for (int j = 1; j < 12; ++j) {
            if (arr[j] < arr[j - 1]) {
                int num = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = num;
            }
        }
    }

    //从小到大排序，上浮的顺序。优化后
    for (int i = 0; i < 11; ++i) {
        _Bool flag = true;
        for (int j = 1; j < 12 - i; ++j) {
            if (arr[j] < arr[j - 1]) {
                int num = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = num;
                flag = false;
            }
        }
        if (flag) break;
    }

    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

//斐波那契数列：1，1，2，3，5，8，13，21，34，55，89...，从第三个数开始，每个数字的值都是前两个数字的和
//获取斐波那契数列上任意一位的数字
//基于数组，动态规划的思想解决，将大问题拆分成小问题
int fibonacciSequence(int target) {
    if (target < 1) return 0;
    if (target == 1 || target == 2) return 1;
    int arr[target];
    arr[0] = arr[1] = 1;
    for (int i = 2; i < sizeof(arr) / sizeof(arr[0]); ++i) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[target - 1];
}

//斐波那契数列解法二（优化占用空间）
int fibonacciSequence2(int target) {
    if (target < 1) return 0;
    if (target == 1 || target == 2) return 1;
    int arr[3];
    arr[0] = arr[1] = 1;
    unsigned int num = 2;
    while (1) {
        arr[2] = arr[1] + arr[0];
        arr[0] = arr[1];
        arr[1] = arr[2];
        num++;
        if (num == target) break;
    }
    return arr[2];
}

/**
 *打家劫舍
 *来源：力扣（LeetCode）No.198 打家劫舍**：https://leetcode.cn/problems/house-robber/
 *
 *你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *给定一个代表每个房屋存放金额的非负整数数组，计算你 **不触动警报装置的情况下** ，一夜之内能够偷窃到的最高金额。
 *
 *示例 1：
 *
 *输入：[1,2,3,1]
 *输出：4
 *解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *  	  偷窃到的最高金额 = 1 + 3 = 4 。
 *
 *示例 2：
 *
 *输入：[2,7,9,3,1]
 *输出：12
 *解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 *  	  偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 */
int rob(int *nums, int numsSize) {
    if (numsSize == 0) return 0;
    if (numsSize == 1) return nums[0];
    if (numsSize == 2) return max(nums[1], nums[0]);

    int dp[numsSize];
    dp[0] = nums[0];
    dp[1] = max(nums[1], nums[0]);

    for (int i = 2; i < numsSize; ++i) {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    return dp[numsSize - 1];
}

int main() {
    bubblingSort();
    printf("%d \n", fibonacciSequence(6));
    printf("%d \n", fibonacciSequence2(8));
    int arr[5] = {2,4,7,115,8};
    printf("%d", rob(arr,5));
    return 0;
}
